package leetcode_500;

import java.util.Random;
import java.util.TreeMap;

/**
 *@author 周杨
 *RandomPointInNonOverlappingRectangles_497 
 *describe:AC 17%
 *2018年9月4日 下午6:51:54
 */
public class RandomPointInNonOverlappingRectangles_497 {
	 TreeMap<Integer, Integer> map;
	    int[][] arrays;
	    int sum;
	    Random rnd= new Random();
	    
	    public RandomPointInNonOverlappingRectangles_497(int[][] rects) {
	        arrays = rects;
	        map = new TreeMap<>();
	        sum = 0;
	        
	        for(int i = 0; i < rects.length; i++) {
	            int[] rect = rects[i];
							
	            // the right part means the number of points of this rectangle, rather than its area
	            // coz ractangles gonna get picked by the num of points
	            sum += (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
	            map.put(sum, i);
	        }
	    }
	    
	    public int[] pick() {
	        // nextInt(sum) returns a num in [0, sum -1]. After added by 1, it becomes [1, sum]
	        int c = map.ceilingKey( rnd.nextInt(sum) + 1);
	        
	        return pickInRect(arrays[map.get(c)]);
	    }
	    
	    private int[] pickInRect(int[] rect) {
	        int left = rect[0], right = rect[2], bot = rect[1], top = rect[3];
	        
	        return new int[]{left + rnd.nextInt(right - left + 1), bot + rnd.nextInt(top - bot + 1) };
	    }
	
}
